package com.sheng.leetcode.year2022.month07.day19;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/07/19
 *
 * 731. 我的日程安排表 II
 *
 * 实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。
 * MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，
 * 注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end。
 * 当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。
 * 每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。
 * 请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
 *
 * 示例：
 *
 * MyCalendar();
 * MyCalendar.book(10, 20); // returns true
 * MyCalendar.book(50, 60); // returns true
 * MyCalendar.book(10, 40); // returns true
 * MyCalendar.book(5, 15); // returns false
 * MyCalendar.book(5, 10); // returns true
 * MyCalendar.book(25, 55); // returns true
 * 解释：
 * 前两个日程安排可以添加至日历中。 第三个日程安排会导致双重预订，但可以添加至日历中。
 * 第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。
 * 第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。
 * 第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；
 * 时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。
 *
 * 提示：
 *
 * 每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
 * 调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/my-calendar-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0731 {

    @Test
    public void test01() {
        MyCalendarTwo obj = new MyCalendarTwo();
        System.out.println(obj.book(10, 20));
        System.out.println(obj.book(50, 60));
        System.out.println(obj.book(10, 40));
        System.out.println(obj.book(5, 15));
        System.out.println(obj.book(5, 10));
        System.out.println(obj.book(25, 55));
    }

}
class MyCalendarTwo {

    List<Integer> startList;
    List<Integer> endList;

    public MyCalendarTwo() {
        startList = new ArrayList<>();
        endList = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        int size = startList.size();
        //index代表重合区域的个数
        int index = 0;
        //保存当前日程和之前日程的重合区域
        int[][] ints = new int[size][2];
        for (int i = 0; i < startList.size(); i++) {
            Integer key = startList.get(i);
            Integer value = endList.get(i);
            //获取重合区域并保存到ints中
            if (start >= key && start < value) {
                ints[index][0] = start;
                ints[index][1] = value;
                index++;
            } else if (end > key && end <= value) {
                ints[index][0] = key;
                ints[index][1] = end;
                index++;
            } else if (start <= key && end >= value) {
                ints[index][0] = key;
                ints[index][1] = value;
                index++;
            }
            //判断重合部位是否存在重复
            if (index >= 2) {
                for (int j = 0; j < index; j++) {
                    int start1 = ints[j][0];
                    int end1 = ints[j][1];
                    for (int k = j + 1; k < index; k++) {
                        int key1 = ints[k][0];
                        int value1 = ints[k][1];
                        //判断是否存在重合，存在则代表存在三重预定，返回false
                        if ((start1 >= key1 && start1 < value1) || (end1 > key1 && end1 <= value1) || (start1 <= key1 && end1 >= value1)) {
                            return false;
                        }
                    }
                }
            }
        }
        //当前日程和之前的日程不存在三重预定
        startList.add(start);
        endList.add(end);
        return true;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */

//和 729. 我的日程安排表 I 几乎完全一致，只需要将对「线段树」所维护的节点信息进行调整即可。
//
//线段树维护的节点信息包括：
//ls/rs: 分别代表当前节点的左右子节点在线段树数组 tr 中的下标；
//add: 懒标记；
//max: 为当前区间的最大值。
//对于常规的线段树实现来说，都是一开始就调用 build 操作创建空树，而线段树一般以「满二叉树」的形式用数组存储，
//因此需要 4×n 的空间，并且这些空间在起始 build 空树的时候已经锁死。
//如果一道题仅仅是「值域很大」的离线题（提前知晓所有的询问），我们还能通过「离散化」来进行处理，将值域映射到一个小空间去，从而解决 MLE 问题。
//但对于本题而言，由于「强制在线」的原因，我们无法进行「离散化」，同时值域大小达到 1e9 级别，因此如果我们想要使用「线段树」进行求解，只能采取「动态开点」的方式进行。
//动态开点的优势在于，不需要事前构造空树，而是在插入操作 add 和查询操作 query 时根据访问需要进行「开点」操作。由于我们不保证查询和插入都是连续的，
//因此对于父节点 u 而言，我们不能通过 u << 1 和 u << 1 | 1 的固定方式进行访问，
//而要将节点 tr[u] 的左右节点所在 tr 数组的下标进行存储，分别记为 ls 和 rs 属性。
//对于 tr[u].ls = 0 和 tr[u].rs = 0 则是代表子节点尚未被创建，当需要访问到它们，而又尚未创建的时候，则将其进行创建。
//由于存在「懒标记」，线段树的插入和查询都是 log{n} 的，因此我们在单次操作的时候，
//最多会创建数量级为 log{n} 的点，因此空间复杂度为 O(m log{n})，而不是 O(4×n)，
//而开点数的预估需不能仅仅根据 log{n} 来进行，还要对常熟进行分析，才能得到准确的点数上界。
//动态开点相比于原始的线段树实现，本质仍是使用「满二叉树」的形式进行存储，只不过是按需创建区间，如果我们是按照连续段进行查询或插入，
//最坏情况下仍然会占到 4×n 的空间，因此盲猜 log{n} 的常数在 4 左右，保守一点可以直接估算到 6，
//因此我们可以估算点数为 6×m×log n，其中 n = 1e9 和 m = 1e3 分别代表值域大小和查询次数。
//当然一个比较实用的估点方式可以「尽可能的多开点数」，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（ Java 的 128M 可以开到 5 * 10^6 以上）。
//
//class MyCalendarTwo {
//    class Node {
//        int ls, rs, add, max;
//    }
//    int N = (int)1e9, M = 120010, cnt = 1;
//    Node[] tr = new Node[M];
//    void update(int u, int lc, int rc, int l, int r, int v) {
//        if (l <= lc && rc <= r) {
//            tr[u].add += v;
//            tr[u].max += v;
//            return ;
//        }
//        lazyCreate(u);
//        pushdown(u);
//        int mid = lc + rc >> 1;
//        if (l <= mid) update(tr[u].ls, lc, mid, l, r, v);
//        if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v);
//        pushup(u);
//    }
//    int query(int u, int lc, int rc, int l, int r) {
//        if (l <= lc && rc <= r) return tr[u].max;
//        lazyCreate(u);
//        pushdown(u);
//        int mid = lc + rc >> 1, ans = 0;
//        if (l <= mid) ans = Math.max(ans, query(tr[u].ls, lc, mid, l, r));
//        if (r > mid) ans = Math.max(ans, query(tr[u].rs, mid + 1, rc, l, r));
//        return ans;
//    }
//    void lazyCreate(int u) {
//        if (tr[u] == null) tr[u] = new Node();
//        if (tr[u].ls == 0) {
//            tr[u].ls = ++cnt;
//            tr[tr[u].ls] = new Node();
//        }
//        if (tr[u].rs == 0) {
//            tr[u].rs = ++cnt;
//            tr[tr[u].rs] = new Node();
//        }
//    }
//    void pushup(int u) {
//        tr[u].max = Math.max(tr[tr[u].ls].max, tr[tr[u].rs].max);
//    }
//    void pushdown(int u) {
//        tr[tr[u].ls].add += tr[u].add; tr[tr[u].rs].add += tr[u].add;
//        tr[tr[u].ls].max += tr[u].add; tr[tr[u].rs].max += tr[u].add;
//        tr[u].add = 0;
//    }
//    public boolean book(int start, int end) {
//        if (query(1, 1, N + 1, start + 1, end) >= 2) return false;
//        update(1, 1, N + 1, start + 1, end, 1);
//        return true;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/my-calendar-ii/solution/by-ac_oier-a1b3/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
